Méthode de type off-policy avec approximations

7. L'erreur de Bellman n'est pas apprenable

7.1. Concept d'apprenabilité

Dans ce qui suit, nous désignons une quantité comme étant apprenable si nous pouvons l'apprendre à partir d'un nombre fini ou infini d'expériences. Dans le domaine de l'apprentissage automatique, un grand nombre de quantités ne sont pas apprenables, même avec un nombre infini d'expériences. Ces quantités peuvent être calculées ou estimées si la structure de l'environnement est totalement connue, mais ne le peuvent plus à l'aide uniquement de résultats d'expériences tels que les séquences d'actions et des récompenses. On dit alors qu'elles ne sont pas apprenables. Nous allons voir que la fonction d'objectif construite avec l'erreur de Bellman $\overline {BE}$ n'est pas apprenable.

Pour se familiariser davantage avec le concept d'apprenabilité, considérons l'exemple suivant, dans lequel les transitions sont considérées comme équiprobables (les numéros indiquent les récompenses obtenues). Le vecteur poids $\textbf{w}$ ne possède qu'une seule composante $w$. Chaque état ne produit qu'une seule composante du vecteur caractéristique $x=1$.

Le MDP de gauche se trouve toujours dans le même état et produit une séquence de récompenses contenant une suite infinie de $0$ et de $2$, de manière aléatoire, avec une probabilité d'apparition pour chacune de ces valeurs de $p=0.5$.

Le MDP de droite, à chaque pas, reste soit dans l'état courant ou passe sur l'autre état, cela de manière équiprobable. Les récompenses sont déterministes, et valent toujours 0 depuis l'état de gauche et toujours 2 depuis l'état de droite. Cependant, comme chaque état apparait de manière équiprobable, les observations des récompenses sont également une séquence de $0$ et de $2$ apparaissant de manière aléatoire, dont chaque valeur a une probabilité $p=0.5$ d'apparaître.

Ces deux MDP produisent donc les mêmes observations de récompenses et il découle que même si le nombre d'observations est infini, il sera impossible de déterminer si ces observations sont issues du MDP de gauche ou de droite. On ne pourra pas dire si le MDP possède un ou deux états, ni s'il est stochastique ou déterministe. Ces quantités ne sont donc pas apprenables.

7.2. La fonction d'objectif $\overline {VE}$ n'est pas apprenable

Rappelons l'expression de la fonction objectif $\overline {VE}$:

$$\overline {VE} \left( \textbf{w} \right) = \sum\limits_{s \in S} {\mu \left( s \right)} {\left[ {{v_\pi }\left( s \right) - \hat v\left( {s,\textbf{w}} \right)} \right]^2}$$

Si nous prenons $\gamma=0$, alors les vraies valeurs des états (en partant de la gauche) sont $1$, $0$ et $2$. Supposons maintenant que $w=1$. Dans ce cas, si on assume que ${\mu \left( s \right)}$ est identique pour les deux états du MDP de droite :

• $\overline {VE} = 1 \cdot {\left( {1 - 1} \right)^2} = 0$ pour le MDP de gauche
• $\overline {VE} = 0,5 \cdot {\left( {0 - 1} \right)^2} + 0,5 \cdot {\left( {2 - 1} \right)^2} = 1$ pour le MDP de droite.

Les valeurs de la fonction d'objectif $\overline {VE}$ sont donc différentes dans les deux cas, alors que les observations générées possèdent la même distribution. L'erreur $\overline {VE}$ ne peut donc pas être apprise.

7.3. La fonction d'objectif $\overline {VE}$ est quand même utile

On remarque dans l'exemple précédent que la solution $w=1$ est optimale dans les deux cas. On peut alors se demander s'il s'agit d'une coïncidence ou si, de manière générale, tous les MDP avec la même distribution des données observées possèdent le même vecteur poids optimum... Si cela est vrai, alors on peut dire que la fonction d'objectif $\overline {VE}$ est utile dans le sens où même si elle n'est pas apprenable, le paramètre qui l'optimise l'est !

Pour vérifier que c'est bien la cas, utilisons cette fois-ci une erreur qui est clairement apprenable. Prenons la valeur quadratique moyenne de l'erreur sur le gain $\overline {RE}$ (objectif de type Monte-Carlo) qui est uniquement déterminée par la distribution des résultats d'observations :

$$\overline {RE} = E\left[ {{{\left( {{G_t} - \hat v\left( {{S_t},\textbf{w}} \right)} \right)}^2}} \right]$$

Si on développe l'expression de cette erreur, on peut faire apparaitre notre fonction objectif $\overline {VE}$ et faire un lien avec celle-ci:

$\overline {RE} = E\left[ {{{\left( {{G_t} - \hat v\left( {{S_t},\textbf{w}} \right)} \right)}^2}} \right]$

$ \quad \: \: \: \: = \sum\limits_{s \in S} {\mu \left( s \right)} \left[ {{{\left( {{G_t} - \hat v\left( {{S_t},\textbf{w}} \right)} \right)}^2}} \right]$

$ \quad \: \: \: \: = \sum\limits_{s \in S} {\mu \left( s \right)} \left[ {{{\left( {\left( {{G_t} - {v_\pi }\left( s \right)} \right) + \left( {{v_\pi }\left( s \right) - \hat v\left( {{S_t},\textbf{w}} \right)} \right)} \right)}^2}} \right]$

$ \quad \: \: \: \: = \sum\limits_{s \in S} {\mu \left( s \right)} \left[ {{{\left( {{G_t} - {v_\pi }\left( s \right)} \right)}^2} + 2\underbrace {\left( {{G_t} - {v_\pi }\left( s \right)} \right)}_{E\left[ {{G_t} - {v_\pi }\left( s \right)} \right] = 0}\left( {{v_\pi }\left( s \right) - \hat v\left( {{S_t},\textbf{w}} \right)} \right) + {{\left( {{v_\pi }\left( s \right) - \hat v\left( {{S_t},\textbf{w}} \right)} \right)}^2}} \right]$

$ \quad \: \: \: \: = \sum\limits_{s \in S} {\mu \left( s \right)} \left[ {{{\left( {{G_t} - {v_\pi }\left( s \right)} \right)}^2} + {{\left( {{v_\pi }\left( s \right) - \hat v\left( {{S_t},\textbf{w}} \right)} \right)}^2}} \right]$

$ \quad \: \: \: \: = E\left[ {{{\left( {{G_t} - {v_\pi }\left( s \right)} \right)}^2}} \right] + E\left[ {{{\left( {{v_\pi }\left( s \right) - \hat v\left( {{S_t},\textbf{w}} \right)} \right)}^2}} \right]$

$ \overline {RE} = E\left[ {{{\left( {{G_t} - {v_\pi }\left( s \right)} \right)}^2}} \right] + \overline {VE} \left( \textbf{w} \right)$

On remarque que les deux fonctions sont identiques à un coefficient près, qui ne dépend pas du paramètre $\textbf{w}$. Ces deux fonctions d'objectif doivent donc partager la valeur optimale du paramètre ${\textbf{w}^*}$.

Deux MDP différents peuvent donc produire des distributions d'observations identiques mais des valeurs différentes d'objectifs $\overline {VE}$, ce qui prouve que la fonction d'objectif $\overline {VE}$ ne peut pas être estimée à partir de l'observation des expériences, et n'est donc pas apprenable. Cependant, ces fonctions d'objectifs partagent le même paramètre optimal ${\textbf{w}^*}$. De plus, ce paramètre optimal peut être estimé à partir d'une autre fonction objectif, $\overline {RE}$, qui elle est uniquement déterminée par la distribution des données et est donc apprenable :

7.4. L'erreur de Bellman n'est pas apprenable

Revenons à présent sur l'erreur de Bellman $\overline {BE}$. Rappelons que l'erreur de Bellman correspond à l'espérance de l'erreur TD :

$$\overline {BE} = {E}\left[ {{R_{t + 1}} + \gamma {v_\textbf{w}}\left( {{S_{t + 1}}} \right) - {v_\textbf{w}}\left( {{S_t}} \right)|{S_t} = s,{A_t} \sim \pi } \right]$$

Nous allons voir que l'erreur $\overline {BE}$ est identique à l'erreur $\overline {VE}$ dans le sens où elle ne peut pas être estimée à partir des seuls retours d'expériences. Pour la calculer, il faut connaître le modèle complet de l'environnement. Mais elle est différente de l'erreur $\overline {VE}$ car le paramètre optimal qui minimise la solution n'est pas apprenable.

L'exemple ci-dessous illustre cette différence. Ces deux MDP génère une distribution identique mais les paramètres optimaux ne sont pas identiques, ce qui montre que le vecteur poids n'est pas apprenable dans ce cas car il n'est pas fonction des données observées.

Considérons donc les deux MDP ci-dessous pour lesquels les transitions sont considérées équiprobables et les nombres indiquent les récompenses obtenues. Le vecteur poids possède deux composantes : $\textbf{w} = \left( {{w_1},{w_2}} \right)$. Le MDP de gauche possède deux états distincts. Le MDP de droite possède lui trois états, mais deux d'entre eux (B et B') partagent la même composante $w_2$ du vecteur poids, alors que l'état A est caractérisé par la première composante du vecteur poids. L'ensemble des deux états {B+B'} est donc vu par l'approximateur comme un seul état, équivalent à l'état B du premier MDP. Le second MDP a été structuré de manière à ce que le temps passé dans chaque état soit le même, c'est-à-dire que $\mu \left( s \right) = \frac{1}{3}$, pour tous les états $s$ du MDP.

Les observations des récompenses sont identiques sur les deux MDP. Dans les deux cas, lorsque l'agent se trouve sur l'état A, il verra une récompense de 0 suivi par quelques apparitions de l'état B avec des récompenses de -1, sauf la dernière récompense qui sera égale à 1 et dont l'état suivant sera l'état A. Ce schéma se répètera par la suite. Dans les deux MDP, la probabilité d'obtenir une séquence de $k$ B vaut ${2^{ - k}}$ :

Supposons maintenant que $\textbf{w}=\textbf{0}$. Dans le premier MDP, il s'agit de la solution exacte. L'erreur de Bellman est donc nulle. Dans le second MDP, cette solution produit les erreurs quadratiques suivantes:

• ${\left\| {\overline {BE} \left( A \right)} \right\|^2} = {\left\| {0,5 \cdot \left[ {0 + \gamma \cdot 0 - 0} \right] + 0,5 \cdot \left[ {0 + \gamma \cdot 0 - 0} \right]} \right\|^2} = 0$

• ${\left\| {\overline {BE} \left( B \right)} \right\|^2} = {\left\| {1 \cdot \left[ {1 + \gamma \cdot 0 - 0} \right]} \right\|^2} = 1$

• ${\left\| {\overline {BE} \left( {B'} \right)} \right\|^2} = {\left\| {0,5 \cdot \left[ { - 1 + \gamma \cdot 0 - 0} \right] + 0,5 \cdot \left[ { - 1 + \gamma \cdot 0 - 0} \right]} \right\|^2} = 1$

La valeur quadratique moyenne de l'erreur de Bellman sur l'ensemble {B+B'} est donc :

$$\left\| {\overline {BE} \left( {B + B'} \right)} \right\|_\mu ^2 = \mu \left( B \right) \cdot 1 + \mu \left( {B'} \right) \cdot 1 = \frac{2}{3}$$

Ces deux MDP génère donc une même distribution de données mais des erreurs de Bellman différentes. L'erreur de Bellman n'est donc pas apprenable.

7.5. L'erreur de Bellman ne partage pas les paramètres optimaux

Pour le premier MDP, $\textbf{w}=\textbf{0}$ minimise l'erreur de Bellman quelle que soit la valeur de $\gamma$. En effet, pour le premier MDP on a :

• $\left\| {\overline {BE} \left( A \right)} \right\|_\mu ^2 = \left\| {1 \cdot \left[ {0 + \gamma \cdot \hat v\left( B \right) - \hat v\left( A \right)} \right]} \right\|_\mu ^2 = \mu \left( A \right){\left\| {1 \cdot \left[ {0 + \gamma \cdot \hat v\left( B \right) - \hat v\left( A \right)} \right]} \right\|^2} = 0,5 \cdot {\left\| {1 \cdot \left[ {\gamma \cdot \hat v\left( B \right) - \hat v\left( A \right)} \right]} \right\|^2}$

• $\left\| {\overline {BE} \left( B \right)} \right\|_\mu ^2 = \left\| {0,5 \cdot \left[ {1 + \gamma \cdot \hat v\left( A \right) - \hat v\left( B \right)} \right] + 0,5 \cdot \left[ { - 1 + \gamma \cdot \hat v\left( B \right) - \hat v\left( B \right)} \right]} \right\|_\mu ^2 = \left\| {0,5 \cdot \left[ {\gamma \cdot \hat v\left( A \right)} \right] + 0,5 \cdot \left[ {\gamma \cdot \hat v\left( B \right)} \right]} \right\|_\mu ^2$

$\quad \quad \quad \quad \quad \quad \quad = 0,5 \cdot {\left\| {0,5 \cdot \gamma \cdot \hat v\left( A \right) + 0,5 \cdot \gamma \cdot \hat v\left( B \right)} \right\|^2}$

Si $\textbf{w}=\textbf{0}$, on obtient $\left\| {\overline {BE} \left( A \right)} \right\|_\mu ^2 = \left\| {\overline {BE} \left( B \right)} \right\|_\mu ^2 =0$ et cela pour toute valeur de $\gamma$.

Pour le second MDP, la valeur optimale de $\textbf{w}$ est plus complexe et est fonction de $\gamma$:

• $\left\| {\overline {BE} \left( A \right)} \right\|_\mu ^2 = \left\| {0,5 \cdot \left[ {0 + \gamma \cdot \hat v\left( {B'} \right) - \hat v\left( A \right)} \right] + 0,5 \cdot \left[ {0 + \gamma \cdot \hat v\left( B \right) - \hat v\left( A \right)} \right]} \right\|_\mu ^2$

$\quad \quad \quad \quad \quad \left( {\hat v\left( B \right) = \hat v\left( {B'} \right)} \right) \Rightarrow \left\| {\overline {BE} \left( A \right)} \right\|_\mu ^2 = \left\| {\left[ {\gamma \cdot \hat v\left( B \right) - \hat v\left( A \right)} \right]} \right\|_\mu ^2$

$\quad \quad \left\| {\overline {BE} \left( A \right)} \right\|_\mu ^2 = \frac{1}{3}{\left\| {\left[ {\gamma \cdot \hat v\left( B \right) - \hat v\left( A \right)} \right]} \right\|^2}$

• $\left\| {\overline {BE} \left( B \right)} \right\|_\mu ^2 = \left\| {1 \cdot \left[ {1 + \gamma \cdot \hat v\left( A \right) - \hat v\left( B \right)} \right]} \right\|_\mu ^2 = \frac{1}{3}{\left\| {\left[ {1 + \gamma \cdot \hat v\left( A \right) - \hat v\left( B \right)} \right]} \right\|^2}$

• $\left\| {\overline {BE} \left( {B'} \right)} \right\|_\mu ^2 = \left\| {0,5 \cdot \left[ { - 1 + \gamma \cdot \hat v\left( B \right) - \hat v\left( {B'} \right)} \right] + 0,5 \cdot \left[ { - 1 + \gamma \cdot \hat v\left( {B'} \right) - \hat v\left( {B'} \right)} \right]} \right\|_\mu ^2$

$\quad \quad \quad \quad \quad \quad \quad = \left\| {\left[ { - 1 + \gamma \cdot \hat v\left( B \right) - \hat v\left( B \right)} \right]} \right\|_\mu ^2$

Donc sur l'ensemble {B+B'} on a :

$${\left\| {\overline {BE} \left( {B + B'} \right)} \right\|^2} = \frac{1}{3}{\left\| {1+\gamma \cdot \hat v\left( A \right) - \hat v\left( B \right)} \right\|^2} + \frac{1}{3}{\left\| {\left[ { - 1 + \gamma \cdot \hat v\left( B \right) - \hat v\left( B \right)} \right]} \right\|^2}$$

La condition à remplir est donc :

$$\mathop {\min }\limits_\textbf{w} \frac{1}{3}{\left\| {\gamma \cdot {w_2} - {w_1}} \right\|^2} + \frac{1}{3}{\left\| {1 + \gamma \cdot {w_1} - {w_2}} \right\|^2} + \frac{1}{3}{\left\| { - 1 + \left( {\gamma - 1} \right) \cdot {w_2}} \right\|^2}$$

La solution dépend donc de $\gamma$ et si par exemple $\gamma=1$, on peut vérifier que la solution optimale n'est pas la même que pour le premier MDP !

En effet, dans le cas où $\textbf{w}=\textbf{0}$, on obtient $\left\| {\overline {BE} \left( A \right)} \right\|_\mu ^2 = 0$ et ${\left\| {\overline {BE} \left( {B + B'} \right)} \right\|^2} =\frac{2}{3}$. Mais prenons par exemple $\textbf{w}=(-1/2;0)$. Dans ce cas, si $\gamma=1$, on obtient $\left\| {\overline {BE} \left( A \right)} \right\|_\mu ^2 = 1/12$ et ${\left\| {\overline {BE} \left( {B + B'} \right)} \right\|^2} =5/12$ soit un total de $3/6$ ce qui est plus faible que la solution donnée avec $\textbf{w}=(0,0)$. On remarque donc que les valeurs optimales obtenues avec l'erreur de Bellman ne sont pas partagées :

7.6. Objectifs de type Bootstrap

Les autres fonctions d'objectif que nous avons étudiées, c'est-à-dire les erreurs $\overline {TDE}$ (valeur quadratique moyenne de l'erreur TD) et $\overline {PBE}$ (projeté de l'erreur de Bellman), sont des fonctions objectifs de la catégories "Bootstrap". Elles peuvent être estimées à partir des données (elles sont apprenables) et les solutions obtenues sont différentes en fonction de l'objectif utilisé ainsi que du minimum trouvé avec l'erreur de Bellman :

7.7. Conclusion

Pour conclure, on peut dire que:

• L'erreur $\overline {BE}$ n'est pas apprenable ; elle ne peut pas être estimée à partir des données issues de l'expérience.
• L'erreur de Bellman n'est donc utilisable que lorsque le modèle de l'environnement est totalement connu.

En outre, nous avons également montré que l'objectif $\overline {TDE}$ sur lequel repose l'algorithme naïf du gradient ne permet pas d'obtenir les vraies valeurs des états.

Tout cela va donc nous mener à étudier des méthodes permettant de minimiser la fonction d'objectif $\overline {PBE}$.